1. Field of the Invention
The present invention pertains to the correction of errors in a data stream such as that acquired from a storage medium, particularly when an estimate of reliability of the data is provided.
2. Related Art and Other Considerations
It is important that data be accurately transmissible from a source to a destination, since many operations depend upon the integrity of the data obtained from the source. Often the source of data utilized for a particular operation is a data storage medium and the destination is a computer or the like. The data storage medium can take various forms, such as a magnetic disk transduced by a magnetic disk drive or an optical disk transduced by an optical disk drive, for example.
On occasion the data may not be correctly read from the data storage medium or not correctly transmitted along a read channel of the drive to the destination. Fortunately, some apparatus that read or transmit data from a source to a destination, e.g., disk drives, have capabilities for attempting to detect and/or correct errors in the data stream from the source.
There is a substantial body of prior art directed to various techniques for error correction of data. Included in this body of prior art are numerous employments of xe2x80x9cproduct codesxe2x80x9d or two-dimensional codes. As used herein, xe2x80x9cproduct codesxe2x80x9d typically operate upon a matrix of data, with a first parity or code operation being performed upon a row of the matrix (horizontal) and a second parity or code operation being performed upon a column of the matrix (vertical). The horizontal and vertical codes may be employed in alternating sequence for resolving errors in the matrix.
It is known that some types of read channels are particular prone to suffer the prevalence of certain types of errors (e.g., single bits, tribits, etc.). In addition, various techniques have been introduced for obtaining a reliability estimate of data transmitted from a source to a destination. One such technique is referred to as the soft output Viterbi algorithm (SOVA), and is documented, e.g., by Hagenauer and Hoeher, xe2x80x9cA Viterbi Algorithm with Soft-Decision Outputs and Its Applicationsxe2x80x9d, Conference Record, IEEE Global Telecommunications Conference and Exhibition, Dallas, Tex., Nov. 27-30, 1989, Vol. 3, pp. 1680-1686. The SOVA technique assigns a reliability value to each bit in the data stream. Other techniques for obtaining reliability estimates also exist, such as that referenced as the xe2x80x9cBCJRxe2x80x9d algorithm [L. R. Bahl et al., xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, IEEE Tranactions On Information Theory, March 1974, pp. 284-287].
What is needed, and thus an object of the present invention, is an effective way to use reliability information in error detection/location schemes which operate upon a matrix.
In accordance with method and apparatus of the present invention, data obtained from a transmission channel is conceptualized as a matrix. Erroneous column(s) in the matrix are first determined on the basis of column parity violation. An error instance in the matrix is next ascertained by matching the erroneous column(s) with an error event characteristic of the transmission channel. A candidate error row is then located in the matrix with respect to the error instance. Lastly, positions in the matrix specified by an intersection of the candidate error row and the erroneous column(s) of the error instance are corrected.
Data reliability values assigned to positions of the matrix are used to determine the candidate error row. In particular, with respect to the erroneous column(s) of the error instance, and for each of plural rows of the matrix, factors related to reliability values assigned to positions of the matrix are summed to determine a least reliable row as the candidate error row. In an illustrated embodiment, squares of the reliability values are summed to determine a least reliable row, the least reliable row having an extreme (e.g., smallest) sum.
In correcting the row of a matrix, the invention is careful not to correct in isolation an odd weight error instance (e.g., an error instance involving an odd number of columns), lest row parity be violated. To this end, when a candidate error row has been selected for an odd weight error instance, the invention presumes that another odd weight error instance also resides in the same row. The correction of two odd weight error instances in the same row therefore does not violate row parity.
Preferably the transmission channel is included in a disk drive, and is one of an EPR4 and E2PR4 read channel. In the case of an EPR4 read channel, the error event characteristic of the transmission channel is one of (1) a di-bit error; (2) a tri-bit error, followed by one or more bits of no error, followed by a single bit error; (3) a single bit error; (4) a tri-bit error; and (5) a quad-bit error.
The operation of the invention is preferably preceded by a row error detection/correction operation which corrects single bit and tri-bit row errors in the matrix.